package IO;

import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;
//简单来讲，尾递归是指在一个方法内部，递归调用后直接return，没有任何多余的指令了。

public class 尾递归 {
	public static void main(String[] args) {
	System.out.println(acc(10));
	System.out.println(accTail(10,0));
	System.out.println(fibTail(5,1,1));
	//1,2,3,5,8,13,21,34,55
	//1,2,3,4,5,6, 7, 8, 9
	}
	//一个递归实现的累加函数,明明最后一个步骤就是调用acc，为啥不是尾递归？
	static int acc(int n){
      if(n == 1){
          return 1;
      }
      return n + acc(n - 1);//返回不是单纯的函数
   }
	/*普通递归执行过程：
	acc(5)
	5+acc(4)
	5+(4+acc(3))
	5+(4+(3+acc(2)))
	5+(4+(3+(2+acc(1))))
	5+(4+(3+(2+1)))
	5+(4+(3+3))
	5+(4+6)
	5+10
	15
	*/
	//实际上，你看到的最后一个步骤不代表从指令层面来讲的最后一步。这个方法的return先拿到acc(n-1)的值，然后再将n与其相
	//加，所以求acc(n-1)并不是最后一步，因为最后还有一个add操作，把上面的代码做个等价逻辑转换就很清晰了。即：
	/*    
	public static int acc(int n){
      if(n == 1){
          return 1;
      }
      int r = acc(n - 1);
      return n + r;
   }
   */

	//累加的尾递归写法是下面这样子的：
	static int accTail(int n, int sum){
      if(n == 1){
          return sum + n;
      }
      return accTail(n - 1,sum + n);//返回一个单纯的函数
	}
	/*
	accTail(5, 0)
	accTail(4, 5)
	accTail(3, 9)
	accTail(2, 12)
	accTail(1, 14)
	accTail(0, 15)
	
	观察到，accTail(x, y)中形式变量y的实际变量值是不断更新的，对比普通递归就很清楚，后者每个acc()调用中y值不变，仅在层级上
	加深。所以，尾递归是把变化的参数传递给递归函数的变量了。怎么写尾递归？形式上只要最后一个return语句是单纯函数就可以。如：
		return tailrec(x+1);
	而：
		return tailrec(x+1) + x;
	则不可以。因为无法更新tailrec()函数内的实际变量，只是新建一个栈。
	 */
	
	//斐波那契数列的尾递归实现
	static int fibTail(int n,int result1,int result2) {
		if (n<=1) {
			return result1;
		}else {
			return fibTail(n-1,result1+result2,result1);
		}
	}
	/*
	1,2,3,5,8,13,21,34,55
	1,2,3,4,5,6, 7, 8, 9
	fibTail(5,1,1)
	fibTail(4,2,1)
	fibTail(3,3,2)
	fibTail(2,5,3)
	fibTail(1,8,5)
	 */
}
/*
尾递归和一般的递归不同在对内存的占用，普通递归创建stack累积而后计算收缩，尾递归只会占用恒量的内存（和迭代一样）。
递归调用的缺点是方法嵌套比较多，每个内部的递归都需要对应的生成一个独立的栈帧，然后将栈帧都入栈后再调用返回，这样相当于浪费了很多的栈空间.
比如普通递归acc(5),执行过程如下

acc(5)
5+acc(4)
5+(4+acc(3))
5+(4+(3+acc(2)))
5+(4+(3+(2+acc(1))))
5+(4+(3+(2+1)))
5+(4+(3+3))
5+(4+6)
5+10
15

迭代：
int sum=0;
for(int i=0;i<=5;i=++){
	sum=sum+i;
}

尾递归：

可见，这个递归操作要同时五个栈帧存在于栈上才能收尾。尾递归要避免的是，嵌套调用的展开导致的多个栈帧并存的情况。
但尾递归由于将外层方法的结果传递给了内层方法，那外层方法实际上没有任何利用价值了，直接从栈里踢出去就行了，所以可以保证同时只有一个栈帧在
栈里存活，节省了大量栈空间。整个逻辑上来讲是这样的：
main方法将accTail(3,0)入栈accTail(3,0)执行n--，sum+=3,将两个结果
传递给下个accTail,即准备执行accTail(2,3)。这时accTail(3,0)生命周期结束，出栈。以此类推，acc(2,3)入栈出
栈，acc(1,5)入栈出栈，最后得到最终结果6。通过上面的逻辑分析，方法内部只是执行一系列操作，将操作结果传递给下一个递归调用，所以完全
可以将调用递归方法之前的逻辑单独抽出来一个没有递归调用的方法，至于递归的逻辑改为由while循环控制调用流程，啥时候结束、啥时候进行下一
次调用。因为刚才讲了，尾递归下次操作之前能够将上次栈帧释放，可以保证只有一个相关的栈帧在栈里，因此改用循环控制足够了用循环
*/